//给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。 
//
// 示例 1: 
//
// 输入: 
//[
//  [1,1,1],
//  [1,0,1],
//  [1,1,1]
//]
//输出: 
//[
//  [1,0,1],
//  [0,0,0],
//  [1,0,1]
//]
// 
//
// 示例 2: 
//
// 输入: 
//[
//  [0,1,2,0],
//  [3,4,5,2],
//  [1,3,1,5]
//]
//输出: 
//[
//  [0,0,0,0],
//  [0,4,5,0],
//  [0,3,1,0]
//] 
//
// 进阶: 
//
// 
// 一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。 
// 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。 
// 你能想出一个常数空间的解决方案吗？ 
// 
// Related Topics 数组 
// 👍 287 👎 0

package leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

//Java：矩阵置零
public class P73SetMatrixZeroes {

    /**
     *
     * 思路：先记录为0的行和列，然后再次遍历将对应的行和列设置为0
     *
     * 执行用时： 3 ms , 在所有 Java 提交中击败了 23.35% 的用户 内存消耗： 41 MB , 在所有 Java 提交中击败了 88.66% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void setZeroes(int[][] matrix) {
            Set<Integer> xSet = new HashSet<>();
            Set<Integer> ySet = new HashSet<>();

            for (int i = 0; i < matrix.length; i++) {
                for (int m = 0; m < matrix[i].length; m++) {
                    if (matrix[i][m] == 0) {
                        if (!xSet.contains(m)) {
                            xSet.add(m);
                        }
                        if (!ySet.contains(i)) {
                            ySet.add(i);
                        }
                    }
                }
            }

            for (int i = 0; i < matrix.length; i++) {
                for (int k = 0; k < matrix[i].length; k++) {
                    if (xSet.contains(k) || ySet.contains(i)) {
                        matrix[i][k] = 0;
                    }
                }
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[][] nums = new int[][]{
                {0, 1, 2, 0},
                {3, 4, 5, 2},
                {1, 3, 1, 5}};
        Solution solution = new P73SetMatrixZeroes().new Solution();
        solution.setZeroes(nums);
        System.out.println(1);
        // TO TEST
    }

}